P4072 [SDOI2016]征途

dp[i][j]=min(dp[i1][k]+(SumjSumk)2)   (0k<j)dp[i][j]=min(dp[i-1][k]+(Sum_j-Sum_k)^2) ~~~ (0 \le k < j)

dp[i][j]=min(dp[i1][k]+Sumj2+Sumk22SumiSumk)   (0k<j)dp[i][j]=min(dp[i-1][k]+Sum_j^2+Sum_k^2-2Sum_iSum_k) ~~~ (0 \le k < j)

dp[i][j]=min(dp[i1][k]+Sumk22SumiSumk)+Sumj2   (0k<j)dp[i][j]=min(dp[i-1][k]+Sum_k^2-2Sum_iSum_k)+Sum_j^2 ~~~ (0 \le k < j)

dp[i1][j]+Sumj22SumiSumj<dp[i1][k]+Sumk22SumiSumkdp[i-1][j]+Sum_j^2-2Sum_iSum_j<dp[i-1][k]+Sum_k^2-2Sum_iSum_k

(dp[i1][j]+Sumj2)(dp[i1][k]+Sumk2)(SumjSumk)>2Sumi\frac{(dp[i-1][j]+Sum_j^2)-(dp[i-1][k]+Sum_k^2)}{(Sum_j-Sum_k)}>2Sum_i

#include <cstdio>

const int MAXN = 3000;
int n , m , Sum[ MAXN + 5 ];
int dp[ MAXN + 5 ][ MAXN + 5 ];
int Que[ MAXN + 5 ] , Head , Tail;

int deltax( int i , int j ) { return Sum[ i ] - Sum[ j ]; }
int deltay( int k , int i , int j ) { return dp[ k - 1 ][ i ] + Sum[ i ] * Sum[ i ] - dp[ k - 1 ][ j ] - Sum[ j ] * Sum[ j ]; }

int main( ) {
	scanf("%d %d",&n,&m);
	for( int i = 1 ; i <= n ; i ++ ) scanf("%d",&Sum[ i ]) , Sum[ i ] += Sum[ i - 1 ];
	for( int i = 1 ; i <= n ; i ++ ) dp[ 1 ][ i ] = Sum[ i ] * Sum[ i ];
	
	for( int i = 2 ; i <= m ; i ++ ) {
		Head = 1 , Tail = 0;
		for( int j = 1 ; j <= n ; j ++ ) {
			for( ; Head < Tail && deltay( i , Que[ Head ] , Que[ Head + 1 ] ) >= 2 * Sum[ j ] * deltax( Que[ Head ] , Que[ Head + 1 ] ) ; Head ++ );
			dp[ i ][ j ] = dp[ i - 1 ][ Que[ Head ] ] + ( Sum[ j ] - Sum[ Que[ Head ] ] ) * ( Sum[ j ] - Sum[ Que[ Head ] ] );
			for( ; Head < Tail && deltay( i , Que[ Tail - 1 ] , Que[ Tail ] ) * deltax( Que[ Tail ] , j ) >= deltay( i , Que[ Tail ] , j ) * deltax( Que[ Tail - 1 ] , Que[ Tail ] ) ; Tail -- );
			Que[ ++ Tail ] = j;
		}
	}
	printf("%d\n", m * dp[ m ][ n ] - Sum[ n ] * Sum[ n ] );
	return 0;
}